/**
 * 数据结构预备知识
 *      1.时间和空间复杂度
 *
 *      2.包装类和简单了解泛型
 */
class MyArray<T> {
    private Object[] array = (T[])new Object[10];

    public void setArray(int pos,T val) {
        array[pos] = val;
    }
    public T getArray(int pos) {
        return (T)array[pos];
    }
}
class Person {
    public String name;
    public int age;
    public Person(String name,int age) {
        this.name = name;
        this.age = age;
    }
}
public class Test {
    /**
     * 包装类和简单了解泛型
     * @param args
     *      1.包装类
     *      2.泛型
     */
    /**
     * 泛型
     * @param args
     *      1.泛型的语法
     *      2.泛型的使用
     *      3.裸类型
     *      4.擦除机制
     */
    public static void main(String[] args) {
        /**
         * 擦除机制
         *      将方法中,所有T类型全部擦除为Object
         *
         * 创建数组->均使用Object,在获取数组下标对应值时,进行强转即可
         */
    }
    public static void main12(String[] args) {
        /**
         * 裸类型
         *      没有类型实参的泛型类
         * 小结:
         *      1.泛型是将数据类型参数化进行传递
         *      2.使用<T>表示是一个泛型类
         *      3.泛型类目前优点:1.数据类型参数化(指定数据类型 ) 2.编译器自动进行转换和检查
         */
    }
    public static void main11(String[] args) {
        /**
         * 使用泛型类的使用
         *      语法:
         *          泛型类<类型实参> 泛型类变量名 = new 泛型类型<类型实参(可省略)>(构造方法实参);
         *      注:只能接受类,其中,基本数据类型类必须时包装类
         *
         * 类型推导:根据泛型类<>中实参来进行判断后面<实参类型>,所以可以直接进行省略
         */
    }
    public static void main10(String[] args) {
        /**
         * 泛型的语法:
         *      1.class 泛型类名称<类型参数列表>
         *      2.class 泛型类名称<类型参数列表> extends 类(泛型类也可以)
         *
         * 注意事项:
         *      1.<T>是占位符,表示当前类是泛型类->还有其它名称,E K V N T S U V
         *      2.不能new泛型类型的数组(因为泛型是编译时期的语法,JVM中不存在该定义)
         *      3.类型后<>加入类型,指定当前泛型类类型
         *      4.使用泛型,不需要进行强转
         *      5.确定类型后,会对数组中的元素类型进行检查
         */
    }
    public static void main9(String[] args) {
        MyArray<Integer> myArray1 = new MyArray<>();
        myArray1.setArray(0,10);
        myArray1.setArray(1,20);

        MyArray<String> myArray2 = new MyArray<>();
        myArray2.setArray(0,"hello");
        myArray2.setArray(1,"world");

        MyArray<Person>  myArray3 = new MyArray<>();
        Person person = new Person("zhangSan",18);myArray3.setArray(0,person);
    }
    /**
     * 包装类
     * @param args
     *      1.基本数据类型和对应的包装类
     *      2.装箱和拆箱
     *      3.自动装箱和拆箱
     */
    public static void main8(String[] args) {
        /**
         * 自动装箱和拆箱
         *      1.直接赋值
         *      2.强转
         */
        int a = 10;
        Integer ii = a;
        Integer ii2 = (Integer)a;

        int a2 = ii;
        int a3 = (int)ii;

        System.out.println(ii);
        System.out.println(ii2);
        System.out.println(a2);
        System.out.println(a3);
    }
    public static void main7(String[] args) {
        /**
         * 装箱和拆箱
         *      装箱:基本数据类型转为包装类型
         *      拆箱:包装类型转为基本数据类型
         */
        int a = 10;
        Integer ii = Integer.valueOf(a);

        Integer ii2 = new Integer(a);
        int aa = ii2.intValue();

        System.out.println(ii);
        System.out.println(aa);
    }
    public static void main6(String[] args) {
        /**
         * 基本数据类型和对应的包装类
         *      1.int->Integer
         *      2.char->Character
         *      3.其它基本类型包装类型为首字母大写
         */
    }
    /**
     * 时间和空间复杂度
     * @param args
     *      1.算法效率
     *      2.时间复杂度
     *      3.空间复杂度
     * 总结
     *      1.时间和空间复杂度必须结合具体代码来进行计算
     *      2.常见复杂度O(1),O(logN),O(N),O(N*logN),O(N^2),O(2^N)
     */
    long factorial2(int N) {//O(N)
        return N < 2 ? N : factorial2(N-1)*N;
    }
   public long[] fibonacci2(int n) {//O(N)
        long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }
    public static void main5(String[] args) {
        /**
         * 空间复杂度:一个算法在运行过程中,临时占用存储空间的大小的量度
         * 表示方法:大O渐进表示法
         */
    }
    /**
     * 时间复杂度
     *      1.时间复杂度的概念
     *      2.大O的渐进表示法
     *      3.推导大O阶方法
     *      4.常见时间复杂度举例
     */
    //常见时间复杂度举例
    void func2(int N) {//O(2*N + 10) = O(N)
        int count = 0;
        for (int k = 0; k < 2 * N ; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0) {
            count++;
        }
        System.out.println(count);
    }
    void func3(int N, int M) {//O(M + N)
        int count = 0;
        for (int k = 0; k < M; k++) {
            count++;
        }
        for (int k = 0; k < N ; k++) {
            count++;
        }
        System.out.println(count);
    }
//    void bubbleSort(int[] array) {//累加公式求和,O((N*(N-1))/2) = O(N ^ 2)
//        for (int end = array.length; end > 0; end--) {
//            boolean sorted = true;
//            for (int i = 1; i < end; i++) {
//                if (array[i - 1] > array[i]) {
//                    Swap(array, i - 1, i);
//                    sorted = false;
//                }
//            }
//            if (sorted == true) {
//                break;
//            }
//        }
//    }
    int binarySearch(int[] array, int value) {//每次减半,n(个数)/2^x(次数)=1,O(log2^N)
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end-begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value)
                end = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    /**
     * 求递归次数
     * @param N
     * @return
     * 递归时间复杂度 = 递归次数 * 递归后方法内部执行次数
     */
    long factorial(int N) {//N * 1(方法内部只进行一次三目运行符比较,故为1)->O(N)
        return N < 2 ? N : factorial(N-1) * N;
    }
    int fibonacci(int N) {//递归次数 = 等比数列求和 * 1(方法内部执行次数)->O(2^N)
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }
    public static void main4(String[] args) {

    }
    public static void main3(String[] args) {
        /**
         * 大O的渐进表示法
         *      大O符号:描述函数渐进行为的数学符号
         *      计算大概执行次数
         *
         * 推导大O阶方法
         *      1.用常数1取代运行时间中的所有加法常数
         *      2.在修改后的运行次数函数中,只保留最高阶项
         *      3.如果最高项存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶
         *
         * 最坏情况:任意输入规模的最大运行次数(上界)
         * 最好情况:任意输入规模的最小运行次数(上界)
         * 平均情况:任意输入规模的期望运行次数
         */
    }
    public static void main2(String[] args) {
        /**
         * 时间复杂度的概念:算法中基本操作的执行次数
         */
    }
    public static void main1(String[] args) {
        /**
         * 算法效率
         *      时间效率->时间复杂度
         *              衡量一个算法的运行速度
         *      空间效率->空间复杂度
         *              衡量一个算法额外需要的空间
         */
    }
}
